package cn.ekuma.util;

public class SortUtil {
	//显示排序结果
		public static <T extends Comparable<? super T>> void show(T[] elem,int n){
			for (int i=0;i<n;i++){
				System.out.print(elem[i]);
				System.out.print(' ');
			}
			System.out.println();
		}
		//交换元素
		private static <T extends Comparable<? super T>> void swap(T[] elem,int i,int j){
			T tmp=elem[i];
			elem[i]=elem[j];
			elem[j]=tmp;
		}
		//直接插入排序法,复杂度为O(n^2)
		public static <T extends Comparable<? super T>> void straightInsertSort (T elem[],int n){
			for (int i=1;i<n;i++){
				T e=elem[i];
				int j;
				for (j=i-1;j>=0 && e.compareTo(elem[j])<0;j--){
					elem[j+1]=elem[j];
				}
				elem[j+1]=e;
			}
		}
		//shell插入排序算法,复杂度为O(n^1.5)
		private static <T extends Comparable<? super T>> void  shellInsertHelp(T elem[],int n,int incr){
			for (int i=incr;i<n;i++){
				T e=elem[i];
				int j=i-incr;
				for (;j>=0 && e.compareTo(elem[j])<0;j=j-incr){
					elem[j+incr]=elem[j];
				}
				elem[j+incr]=e;
				
			}
		}
		public static <T extends Comparable<? super T>> void shellSort(T elem[],int n ){
			for (int incr=n/2;incr>0;incr=incr/2){
				shellInsertHelp(elem,n,incr);
			}
		}
		//冒泡排序算法，时间复杂度为O(n^2)
		public static <T extends Comparable<? super T>> void bubbleSort(T elem[],int n){
			for (int i=n-1;i>0;i--){
				for (int j=0;j<i;j++){
					if (elem[j].compareTo(elem[i])>0){
						swap(elem,i,j);
					}
				}
			}
		}
		//快速排序算法，时间复杂度为O(n*log(n))
		private static <T extends Comparable<? super T>> int partition(T elem[],int low,int high){
			while (low<high){
				for (;elem[high].compareTo(elem[low])>=0 && low<high;high--);
				swap(elem,high,low);
				for (;elem[high].compareTo(elem[low])>=0 && low<high;low++);
				swap(elem,high,low);
			}
			return low;
		}
		private static <T extends Comparable<? super T>> void quickSortHelp(T elem[],int low,int high){
			if (low<high){
				int pivot=partition(elem,low,high);
				quickSortHelp(elem,low,pivot-1);
				quickSortHelp(elem,pivot+1,high);
			}
		}
		public static <T extends Comparable<? super T>> void quickSort(T elem[],int n){
			quickSortHelp(elem,0,n-1);
		}
		//简单选择排序算法，时间复杂度为O(n^2)
		public static <T extends Comparable<? super T>> void simpleSelectionSort(T elem[],int n){
			for (int i=0;i<n-1;i++){
				int lowIdx=i;
				for (int j=i+1;j<n;j++){
					if (elem[lowIdx].compareTo(elem[j])>0)
						lowIdx=j;
				}
				swap(elem,lowIdx,i);
			}
		}
		//堆排序，时间复杂度为O(n*log(n))
		private static <T extends Comparable<? super T>> void heapAdjust(T elem[],int low,int high){
			for (int i=low,lhs=2*i+1 ;lhs<=high;lhs=2*i+1){
				if (lhs<high && elem[lhs].compareTo(elem[lhs+1])<0)lhs++;
				if (elem[i].compareTo(elem[lhs])<0){
					swap(elem,i,lhs);
					i=lhs;
				}else break;
			}
		}
		public static <T extends Comparable<? super T>> void heapSort(T elem[],int n){
			//初始化堆
			for (int i=(n-2)/2;i>=0;i--){
				heapAdjust(elem,i,n-1);
			}
			swap(elem,0,n-1);
			//排序
			for (int i=n-2;i>0;--i){
				heapAdjust(elem,0,i);
				swap(elem,0,i);
			}
		}
		//归并排序算法，时间复杂度为O(n*log(n))
		private static <T extends Comparable<? super T>> void simpleMerge(T elem[],T tmpElem[],int low ,int mid, int high){
			int i=low,j=mid+1,k=low;
			for (;i<=mid && j<=high;k++){
				if (elem[i].compareTo(elem[j])<=0)
					tmpElem[k]=elem[i++];
				else 
					tmpElem[k]=elem[j++];
			}
			for (;i<=mid;i++){
				tmpElem[k++]=elem[i];
			}
			for (;j<=high;j++){
				tmpElem[k++]=elem[j];
			}
			
			for (;low<=high;low++){
				elem[low]=tmpElem[low];
			}
		}
		private static <T extends Comparable<? super T>> void mergeHelp(T elem[],T tmpElem[],int low ,int high){
			if (low < high){
				int mid=(low+high)/2;
				mergeHelp(elem,tmpElem,low,mid);
				mergeHelp(elem,tmpElem,mid+1,high);
				simpleMerge(elem,tmpElem,low,mid,high);
			}
		}
		public static <T extends Comparable<? super T>> void mergeSort(T elem[],int n){
			T[] tmpElem=(T[])new Comparable[n];
			mergeHelp(elem,tmpElem,0,n-1);
		}

}
